{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Generalized Abbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: generateAbbreviations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #列举单词的全部缩写"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>单词的 <strong>广义缩写词</strong> 可以通过下述步骤构造：先取任意数量的 <strong>不重叠、不相邻</strong> 的子字符串，再用它们各自的长度进行替换。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"abcde\"</code> 可以缩写为：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><code>\"a3e\"</code>（<code>\"bcd\"</code> 变为 <code>\"3\"</code> ）</li>\n",
    "\t\t<li><code>\"1bcd1\"</code>（<code>\"a\"</code> 和 <code>\"e\"</code> 都变为 <code>\"1\"</code>）<meta charset=\"UTF-8\" /></li>\n",
    "\t\t<li><code>\"5\"</code>&nbsp;(<code>\"abcde\"</code>&nbsp;变为&nbsp;<code>\"5\"</code>)</li>\n",
    "\t\t<li><code>\"abcde\"</code>&nbsp;(没有子字符串被代替)</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>然而，这些缩写是 <strong>无效的</strong> ：\n",
    "\t<ul>\n",
    "\t\t<li><code>\"23\"</code>（<code>\"ab\"</code> 变为 <code>\"2\"</code> ，<code>\"cde\"</code> 变为 <code>\"3\"</code> ）是无效的，因为被选择的字符串是相邻的</li>\n",
    "\t\t<li><meta charset=\"UTF-8\" /><code>\"22de\"</code>&nbsp;(<code>\"ab\"</code> 变为&nbsp;<code>\"2\"</code>&nbsp;，&nbsp;<code>\"bc\"</code>&nbsp;变为&nbsp;<code>\"2\"</code>) &nbsp;是无效的，因为被选择的字符串是重叠的</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>word</code> ，返回&nbsp;<em>一个由</em>&nbsp;<code>word</code> 的<em>所有可能 <strong>广义缩写词</strong> 组成的列表</em>&nbsp;。按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"word\"\n",
    "<strong>输出：</strong>[\"4\",\"3d\",\"2r1\",\"2rd\",\"1o2\",\"1o1d\",\"1or1\",\"1ord\",\"w3\",\"w2d\",\"w1r1\",\"w1rd\",\"wo2\",\"wo1d\",\"wor1\",\"word\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"a\"\n",
    "<strong>输出：</strong>[\"1\",\"a\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word.length &lt;= 15</code></li>\n",
    "\t<li><code>word</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [generalized-abbreviation](https://leetcode.cn/problems/generalized-abbreviation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [generalized-abbreviation](https://leetcode.cn/problems/generalized-abbreviation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"word\"', '\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        def dfs(abbrev, res, start_idx, convert_last):\n",
    "            if start_idx == len(word):\n",
    "                res.append(''.join(abbrev))\n",
    "                return \n",
    "\n",
    "            for i in range(start_idx, len(word)):\n",
    "                tmp = word[start_idx: i+1]\n",
    "                if convert_last == False:\n",
    "                    dfs(abbrev+[str(i+1-start_idx)], res, i+1, True)\n",
    "                else:\n",
    "                    dfs(abbrev+[tmp], res, i+1, False)\n",
    "\n",
    "            return \n",
    "\n",
    "        res = []\n",
    "        dfs([], res, 0, False)\n",
    "        dfs([], res, 0, True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        n = len(word)\n",
    "        ans = []\n",
    "        for i in range(1 << n):\n",
    "            cnt = 0\n",
    "            s = []\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if cnt:\n",
    "                        s.append(str(cnt))\n",
    "                        cnt = 0\n",
    "                    s.append(word[j])\n",
    "            if cnt:\n",
    "                s.append(str(cnt))\n",
    "            ans.append(''.join(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        def dfs(abbrev, res, start_idx, convert_last):\n",
    "            if start_idx == len(word):\n",
    "                res.append(''.join(abbrev))\n",
    "                return \n",
    "\n",
    "            for i in range(start_idx, len(word)):\n",
    "                tmp = word[start_idx: i+1]\n",
    "                if convert_last == False:\n",
    "                    dfs(abbrev+[str(i+1-start_idx)], res, i+1, True)\n",
    "                else:\n",
    "                    dfs(abbrev+[tmp], res, i+1, False)\n",
    "\n",
    "            return \n",
    "\n",
    "        res = []\n",
    "        dfs([], res, 0, False)\n",
    "        dfs([], res, 0, True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        N = len(word)\n",
    "\n",
    "        def getS(m):\n",
    "            ans = \"\"\n",
    "            t = 0\n",
    "            for i in range(N-1, -1, -1):\n",
    "                bit = ( m >> i ) & 1\n",
    "                if bit:\n",
    "                    ans += (str(t) if t else \"\") + word[N-1-i]\n",
    "                    t = 0\n",
    "                else:\n",
    "                    t += 1\n",
    "            if t:\n",
    "                ans += str(t)\n",
    "            # print(bin(m)[2:].zfill(N), ans)\n",
    "            return ans\n",
    "        \n",
    "        ret = [ str(N) ]\n",
    "        m = M = (1<<N)-1\n",
    "        while m:\n",
    "            ret.append(getS(m))\n",
    "            m = (m-1)&M\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        def dfs(abbrev, res, start_idx, convert_last):\n",
    "            if start_idx == len(word):\n",
    "                res.append(''.join(abbrev))\n",
    "                return \n",
    "\n",
    "            for i in range(start_idx, len(word)):\n",
    "                tmp = word[start_idx: i+1]\n",
    "                if convert_last == False:\n",
    "                    dfs(abbrev+[str(i+1-start_idx)], res, i+1, True)\n",
    "                else:\n",
    "                    dfs(abbrev+[tmp], res, i+1, False)\n",
    "\n",
    "            return \n",
    "\n",
    "        res = []\n",
    "        dfs([], res, 0, False)\n",
    "        dfs([], res, 0, True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        def dfs(abbrev, res, start_idx, convert_last):\n",
    "            if start_idx == len(word):\n",
    "                res.append(''.join(abbrev))\n",
    "                return \n",
    "\n",
    "            for i in range(start_idx, len(word)):\n",
    "                tmp = word[start_idx: i+1]\n",
    "                if convert_last == False:\n",
    "                    dfs(abbrev+[str(i+1-start_idx)], res, i+1, True)\n",
    "                else:\n",
    "                    dfs(abbrev+[tmp], res, i+1, False)\n",
    "\n",
    "            return \n",
    "\n",
    "        res = []\n",
    "        dfs([], res, 0, False)\n",
    "        dfs([], res, 0, True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        def abbre(word):\n",
    "            if not word: return [\"\"],[\"\"]\n",
    "            n = len(word)\n",
    "            ans_w,ans_n = [],[]\n",
    "            for i in range(n):\n",
    "                com_w,com_n = abbre(word[i+1:])\n",
    "                w, num = word[:i+1], str(i+1)\n",
    "                for item in com_w:\n",
    "                   ans_n.append(num+item)\n",
    "                for item in com_n:\n",
    "                    ans_w.append(w+item)\n",
    "            return ans_w, ans_n\n",
    "        w,n = abbre(word)\n",
    "        return w+n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        if len(word) == 0:\n",
    "            return ['']\n",
    "        else:\n",
    "            ret_list = []\n",
    "            for idx in range(len(word)):\n",
    "                prefix = word[: idx + 1]\n",
    "                suffix = word[idx + 1:]\n",
    "                prefix_list = self.generateAbbreviations(suffix)\n",
    "                word1 = str(len(prefix))\n",
    "                word2 = prefix\n",
    "\n",
    "                for item in prefix_list:\n",
    "                    if not item or not item[0].isdigit():\n",
    "                        ret_list.append(word1 + item)\n",
    "\n",
    "                    if not item or item[0].isdigit():   \n",
    "                        ret_list.append(word2 + item)\n",
    "            return ret_list\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        def abbre(word):\n",
    "            if not word: return [\"\"],[\"\"]\n",
    "            n = len(word)\n",
    "            ans_w,ans_n = [],[]\n",
    "            for i in range(n):\n",
    "                com_w,com_n = abbre(word[i+1:])\n",
    "                w, num = word[:i+1], str(i+1)\n",
    "                for item in com_w:\n",
    "                   ans_n.append(num+item)\n",
    "                for item in com_n:\n",
    "                    ans_w.append(w+item)\n",
    "            return ans_w, ans_n\n",
    "        w,n = abbre(word)\n",
    "        return w+n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        def abbre(word):\n",
    "            if not word: return [\"\"],[\"\"]\n",
    "            n = len(word)\n",
    "            ans_w,ans_n = [],[]\n",
    "            for i in range(n):\n",
    "                com_w,com_n = abbre(word[i+1:])\n",
    "                w, num = word[:i+1], str(i+1)\n",
    "                for item in com_w:\n",
    "                   ans_n.append(num+item)\n",
    "                for item in com_n:\n",
    "                    ans_w.append(w+item)\n",
    "            return ans_w, ans_n\n",
    "        w,n = abbre(word)\n",
    "        return w+n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        temp=[0]*len(word)\n",
    "        ret=[]\n",
    "        def dfs(left):\n",
    "            if left==len(word):\n",
    "                i=0\n",
    "                ans=[]\n",
    "                while i<len(word):\n",
    "                    if temp[i]==0:\n",
    "                        ans.append(word[i])\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        count=1\n",
    "                        i+=1\n",
    "                        while i<len(word) and temp[i]==1:\n",
    "                            i+=1\n",
    "                            count+=1\n",
    "                        ans.append(str(count))\n",
    "                ret.append(''.join(ans))\n",
    "            else:\n",
    "                temp[left]=1\n",
    "                dfs(left+1)\n",
    "                temp[left]=0\n",
    "                dfs(left+1)\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "\n",
    "        N = len(word)\n",
    "        ret = []\n",
    "\n",
    "        def dfs(path, i, ct):\n",
    "            if i == N:\n",
    "                if ct:\n",
    "                    ret.append(path + str(ct))\n",
    "                else:\n",
    "                    ret.append(path)\n",
    "                return\n",
    "            dfs(path + (str(ct) if ct else \"\") + word[i], i + 1, 0)\n",
    "            dfs(path, i + 1, ct + 1)\n",
    "\n",
    "        dfs(\"\", 0, 0)\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        res = []\n",
    "        n = len(word)\n",
    "        def dfs(start, ans):\n",
    "            nonlocal res\n",
    "            if start >= n:\n",
    "                res.append(ans)\n",
    "                return\n",
    "\n",
    "            dfs(start + 1, ans + word[start])\n",
    "            for i in range(start, n):\n",
    "                z = word[i + 1] if i + 1 < n else ''\n",
    "                dfs(i + 2, ans + str(i - start + 1) + z)\n",
    "        dfs(0, '')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        # 判断每一个位置是否要变成数字1, 由于每个位置就两种选择可以考虑dfs\n",
    "        def DFS(s, index):\n",
    "            # 第一个 if 用来把1给加到前一位上\n",
    "            if len(s) >= 2 and s[-1].isdigit() and s[-2].isdigit():\n",
    "                x = str(int(s.pop()) + int(s.pop()))\n",
    "                s.append(x)\n",
    "            if index == len(word):\n",
    "                res.append(\"\".join(s))\n",
    "                return\n",
    "            # 变成1\n",
    "            DFS(s+[\"1\"], index+1)\n",
    "            # 不变1\n",
    "            DFS(s+[word[index]], index+1)\n",
    "    \n",
    "\n",
    "        res = []\n",
    "        DFS([], 0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        res = []\n",
    "        n = len(word)\n",
    "        def back(i, temp):\n",
    "            if i == n:\n",
    "                res.append(temp)\n",
    "            else:\n",
    "                for j in range(i, n):\n",
    "                    num = str(j - i) if j - i > 0 else \"\"\n",
    "                    back(j + 1, temp + num + word[j])\n",
    "                back(n, temp + str(n - i))\n",
    "        back(0, \"\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        N = len(word)\n",
    "        def dfs(i, path):\n",
    "            if i > N:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            elif i == N:\n",
    "                path.append(word[i-1])\n",
    "                ans.append(''.join(path))\n",
    "                path.pop()\n",
    "                return\n",
    "            if i > 0:\n",
    "                path.append(word[i-1])\n",
    "            for j in range(i, N+1):\n",
    "                if j > i:\n",
    "                    path.append(str(j-i))\n",
    "                dfs(j+1, path)\n",
    "                if j > i:\n",
    "                    path.pop()\n",
    "            if i > 0:\n",
    "                path.pop()\n",
    "        dfs(0, path)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(index, cur, count):\n",
    "            if index == len(word):\n",
    "                if count > 0:\n",
    "                    cur += str(count)\n",
    "                res.append(cur)\n",
    "                return\n",
    "\n",
    "            # 缩写当前字符: 不添加当前字符到cur中，而是增加计数器\n",
    "            dfs(index + 1, cur, count + 1)\n",
    "            # 不缩写: 把之前count的值放进去，然后加上当前的值（因为不缩写就不用计算Count)\n",
    "            dfs(index + 1, cur + (str(count) if count > 0 else '') + word[index], 0)\n",
    "\n",
    "        dfs(0, '', 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        # 相邻\n",
    "        ans = []\n",
    "        n = len(word)\n",
    "        def dfs(i, pre, ele):\n",
    "            if i == n:\n",
    "                ans.append(''.join(ele))\n",
    "                return\n",
    "            for nex in range(i, n):\n",
    "                if pre:\n",
    "                    ele.append(word[i:nex+1])\n",
    "                    dfs(nex + 1, False, ele)\n",
    "                    ele.pop()\n",
    "                else:\n",
    "                    ele.append(str(nex - i + 1))\n",
    "                    dfs(nex + 1, True, ele)\n",
    "                    ele.pop()\n",
    "        dfs(0, False, [])\n",
    "        dfs(0, True, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        n=len(word)\n",
    "        ans=[]\n",
    "        def dfs(x,ls):\n",
    "            if x==n:\n",
    "                ans.append(\"\".join(ls))\n",
    "                return\n",
    "            for i in range(x,n):\n",
    "                ret=\"\"\n",
    "                if i!=x:\n",
    "                    ret+=str(i-x)\n",
    "                ret+=word[i]\n",
    "                ls.append(ret)\n",
    "                dfs(i+1,ls)\n",
    "                ls.pop()\n",
    "                #if i!=x:\n",
    "                #    ls.pop()\n",
    "            ls.append(str(n-x))\n",
    "            dfs(n,ls)\n",
    "            ls.pop()\n",
    "        dfs(0,[])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]: ### 这个就是生成，跟括号生成很像\n",
    "        # 判断每一个位置是否要变成数字1, 由于每个位置就两种选择可以考虑dfs, 只能用序号取枚举，\n",
    "        def dfs(s,i):\n",
    "            if len(s)>=2 and s[-1].isdigit() and s[-2].isdigit():\n",
    "                x=str(int(s.pop())+int(s.pop()))\n",
    "                s.append(x)\n",
    "            if i==len(word):\n",
    "                res.append(\"\".join(s.copy()))\n",
    "                return \n",
    "            dfs(s+['1'],i+1)\n",
    "            dfs(s+[word[i]],i+1)\n",
    "        res=[]\n",
    "        dfs([],0)\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def DFS(s, index):\n",
    "        #     # 第一个 if 用来把1给加到前一位上\n",
    "        #     #### 这是每一次都会想办法合并，因此从长度大于2就开始合并，也可以想办法在最后的时候进行合并，字母之间的数字全部都加起来，\n",
    "        #     if len(s) >= 2 and s[-1].isdigit() and s[-2].isdigit():\n",
    "        #         x = str(int(s.pop()) + int(s.pop()))\n",
    "        #         s.append(x)\n",
    "        #     if index == len(word):\n",
    "        #         res.append(\"\".join(s))\n",
    "        #         return\n",
    "        #     # 变成1\n",
    "        #     DFS(s+[\"1\"], index+1)\n",
    "        #     # 不变1\n",
    "        #     DFS(s+[word[index]], index+1)\n",
    "    \n",
    "\n",
    "        # res = []\n",
    "        # DFS([], 0)\n",
    "        # return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        N = len(word)\n",
    "        def dfs(i, path, flag):\n",
    "            if i == N:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            path.append(word[i])\n",
    "            dfs(i+1, path, True)\n",
    "            path.pop()\n",
    "            if flag:\n",
    "                for j in range(i+1, N+1):\n",
    "                    path.append(str(j-i))\n",
    "                    dfs(j, path, False)\n",
    "                    path.pop()\n",
    "        dfs(0, path, True)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        l=set()\n",
    "        n=len(word)\n",
    "        s=[]\n",
    "        def dfs(i,is_num):\n",
    "            if i==n:\n",
    "                ss=\"\".join(s)\n",
    "                l.add(ss)\n",
    "                return\n",
    "            if not is_num:\n",
    "                for j in range(i,n):\n",
    "                    s.append(str(j-i+1))\n",
    "                    dfs(j+1,True)\n",
    "                    s.pop()\n",
    "\n",
    "            s.append(word[i])\n",
    "            dfs(i+1,False)\n",
    "            s.pop()\n",
    "        dfs(0,False)\n",
    "        return list(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        n = len(word)\n",
    "        ans = [set()]\n",
    "        def dfs(idx, now):\n",
    "            if idx >= n:\n",
    "                ans[0].add(now)\n",
    "                return\n",
    "            for j in range(idx, n):\n",
    "                lenj = j-idx+1\n",
    "                dfs(j+1, now+word[idx:j+1])\n",
    "                if not now or now[-1].isalpha():\n",
    "                    dfs(j+1, now+str(lenj))\n",
    "        dfs(0, '')\n",
    "        return list(ans[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        @cache\n",
    "        def abbre(word):\n",
    "            if not word: return [\"\"],[\"\"]\n",
    "            n = len(word)\n",
    "            ans_w,ans_n = [],[]\n",
    "            for i in range(n):\n",
    "                com_w,com_n = abbre(word[i+1:])\n",
    "                w, num = word[:i+1], str(i+1)\n",
    "                for item in com_w:\n",
    "                   ans_n.append(num+item)\n",
    "                for item in com_n:\n",
    "                    ans_w.append(w+item)\n",
    "            return ans_w, ans_n\n",
    "        w,n = abbre(word)\n",
    "        return w+n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        @cache\n",
    "        def abbre(word):\n",
    "            if not word: return [\"\"],[\"\"]\n",
    "            n = len(word)\n",
    "            ans_w,ans_n = [],[]\n",
    "            for i in range(n):\n",
    "                com_w,com_n = abbre(word[i+1:])\n",
    "                w, num = word[:i+1], str(i+1)\n",
    "                for item in com_w:\n",
    "                   ans_n.append(num+item)\n",
    "                for item in com_n:\n",
    "                    ans_w.append(w+item)\n",
    "            return ans_w, ans_n\n",
    "        w,n = abbre(word)\n",
    "        return w+n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "import string\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def generateAbbreviations(self, word: str) -> List[str]:\n",
    "        if len(word)==0:\n",
    "            return ['']\n",
    "        ans=[]\n",
    "        for i in range(1,len(word)+1):\n",
    "            prefix=word[0:i]\n",
    "            suffix=word[i:]\n",
    "            abbrs=self.generateAbbreviations(suffix)\n",
    "            for abbr in abbrs:\n",
    "                if abbr=='':\n",
    "                    ans.append(prefix)\n",
    "                    ans.append(str(len(prefix)))\n",
    "                elif abbr[0] in string.ascii_lowercase:\n",
    "                    ans.append(str(len(prefix))+abbr)\n",
    "                else:\n",
    "                    ans.append(prefix+abbr)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
